package SwordFingerOffer;

import java.util.HashMap;
import java.util.Map;

public class Q57_TwoSumEqualS {
    //和为s的两个数字
    //输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。
    // 如果有多对数字的和等于s，则输出任意一对即可。


    //==> 两数之和
    //建立 map 保持映射
    // num -> index
    public int[] twoSum(int[] nums, int target) {

        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])){
                int[] ans = new int[2];
                ans[0] = nums[i];
                ans[1] = target - nums[i];
                return ans;
            }
            map.put(nums[i], i);
        }
        return new int[]{};
    }

    //充分利用有序 ==> 双指针
    public int[] twoSum_1(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right){
            if (nums[left] + nums[right] == target){
                int[] ans = new int[2];
                ans[0] = nums[left];
                ans[1] = nums[right];
                return ans;
            }else if (nums[left] + nums[right] < target){
                left++;
            }else {
                right--;
            }
        }
        return new int[]{};
    }
}
